package main

import "fmt"

func Heapify(arr []int, n int, i int) {
	largest := i
	left := 2*i + 1
	right := 2*i + 2

	if left < n && arr[left] > arr[largest] {
		largest = left
	}

	if right < n && arr[right] > arr[largest] {
		largest = right
	}

	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		Heapify(arr, n, largest)
	}
}

func HeapSort(arr []int) {
	n := len(arr)

	// build max heap
	for i := n/2 - 1; i >= 0; i-- {
		Heapify(arr, n, i)
	}

	// extract elements from heap one by one
	for i := n - 1; i >= 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		Heapify(arr, i, 0)
	}
}

func TestHeapSort() {
	arr := []int{10, 7, 8, 9, 1, 5}
	fmt.Printf("Unsorted array: %v\n", arr)
	HeapSort(arr)
	fmt.Printf("Sorted array: %v\n", arr)
}
